#pragma once

#include<vector>
#include<iostream>
#include<utility>

using namespace std;

template<class K>
struct Hash
{
	size_t operator()(const K& key)
	{
		return key;
	}
};

//为了测试提前写的KeyOfT
template<class K, class T>
struct KeyOfT
{
	const K& operator()(const T& data)
	{
		return data.first;
	}
};

namespace CloseHash
{
	enum Status
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class T>
	struct HashData
	{
		T _data;
		Status _status = EMPTY;
	};

	template<class K, class T, class KeyOfT, class HashFun = Hash<K>>
	class HashTable
	{
	public:
		bool Insert(const T& data)
		{
			KeyOfT kot;
			HashFun hs;

			//判断是否需要扩容
			if (_tables.size() == 0 || _size * 10 / _tables.size() >= 7)
			{
				size_t newSize = _size == 0 ? 10 : 2 * _tables.size();
				HashTable<K, T, KeyOfT, HashFun> newHash;
				newHash._tables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					if (_tables[i]._status == EXIST)
					{
						newHash.Insert(_tables[i]._data);
					}

				}
				_tables.swap(newHash._tables);
				newHash._size = _size;
			}

			size_t start = hs(kot(data)) % _tables.size();
			int i = 1;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					return false;
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			_tables[start]._data = data;
			_tables[start]._status = EXIST;
			_size++;
			return true;
		}
		
		bool Erase(const T& data)
		{
			KeyOfT kot;
			HashFun hs;
			size_t start = hs(kot(data)) % _tables.size();
			int i = 0;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					_tables[start]._status = DELETE;
					return true;
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			//不存在
			return false;
		}
		
		HashData<T>* find(const T& data)
		{
			KeyOfT kot;
			HashFun hs;
			size_t start = hs(kot(data)) % _tables.size();
			int i = 0;
			while (_tables[start]._status == EXIST)
			{
				if (_tables[start]._data == data)
				{
					return &_tables[start];
				}
				start = start + i * i;
				start %= _tables.size();
				i++;
			}
			return nullptr;
		}
	private:
		vector<HashData<T>> _tables;
		size_t _size = 0;
	};

	void test1()
	{
		//T:pair<int, string>
		HashTable<int, pair<int, string>, KeyOfT<int, pair<int, string>>, Hash<int>> hs;
		hs.Insert(make_pair(1, "one"));
		hs.Insert(make_pair(11, "one"));
		hs.Insert(make_pair(12, "two"));
		hs.Insert(make_pair(23, "three"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(63, "three"));
		hs.Insert(make_pair(22, "two"));
		hs.Insert(make_pair(71, "one"));
		hs.Insert(make_pair(62, "two"));
		hs.Insert(make_pair(21, "one"));
		hs.Insert(make_pair(43, "three"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(41, "one"));
		hs.Insert(make_pair(82, "two"));
		hs.Insert(make_pair(3, "three"));
		hs.Insert(make_pair(53, "three"));
		HashData<pair<int, string>>*  ptr = hs.find(make_pair(53, "three"));
		bool ret = hs.Erase(make_pair(53, "three"));
		ptr = hs.find(make_pair(53, "three"));
		ret = hs.Erase(make_pair(53, "three"));
	}
}